package MiddlePractice;

public class Demo55 {
//	55. 跳跃游戏
//	给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
//
//	数组中的每个元素代表你在该位置可以跳跃的最大长度。
//
//	判断你是否能够到达最后一个下标。
	
	public boolean canJump(int[] nums) {
		boolean[] dp = new boolean[nums.length];
		int step=0;
		for(; step<=nums[0]; step++) {
            if(step < nums.length)
			    dp[step] = true;
		}
		
		for(int i=1; i<nums.length; i++) {
			if(dp[i]) {
				
				for(int j=1; j<=nums[i]; j++) {
					if(j + i < nums.length) {
						dp[i + j] = true;
					}
				}
			}
		}
		return dp[nums.length-1];
    }

}
